# -*- coding: utf-8 -*-

'''

@author: wyndem
@Emil:   wyndem.wen@timevary.com
@FileName: chapter_7.py
@Time: 2018/6/27 10:25
@Description: 迪杰斯特拉算法(在含有负数的情况下，不能使用该算法，算出最近的距离)

'''

#每个node只能比一次
processed=[]
#所有的邻居散列表
graph=dict()

start={}
start['a']=5
start['b']=2

graph['start']=start

a={'c':4,'d':2}
graph['a']=a

b={'a':8,'d':7}
graph['b']=b

c={'d':6,'fin':3}
graph['c']=c

d={'fin':1}
graph['d']=d

#终点
graph['fin']={}

#开销表
costs={}
costs['a']=5
costs['b']=2
costs['c']=999
costs['d']=999
costs['fin']=999

#父表
parents={}




def find_lowest_cost_node(costs):
    #当前为无限大
    lowest_cost=float('inf')
    lowest_cost_node=None
    for node in costs:
        cost=costs[node]
        if cost < lowest_cost and node not in processed:
            lowest_cost=cost
            lowest_cost_node=node
    return lowest_cost_node





def find_lowest_ykstl():
    node=find_lowest_cost_node(costs)
    while node is not None:
        cost = costs[node]
        neighbors = graph[node]
        for n,v in neighbors.items():
            new_cost = cost + neighbors[n]
            if costs[n] > new_cost:
                costs[n] = new_cost
                parents[n] = node
        processed.append(node)
        node=find_lowest_cost_node(costs)



if __name__ == '__main__':
    find_lowest_ykstl()
    print(parents)
    print('最短距离：'+str(costs))
